﻿//using System;
//using System.Collections;
//using System.Collections.Generic;
//using System.IO;
//using System.Linq;
//using System.Text;
//using QuickGraph;
//using QuickGraph.Algorithms;
//using QuickGraph.Algorithms.ConnectedComponents;
//using QuickGraph.Algorithms.Search;

//namespace www.coursera.algo.org.ProblemQuestion._4
//{
//    class Program
//    {

//        public static int depth = 0;
//        public static Dictionary<string, int> f;
//        public static Dictionary<string, int> d;
//        public static int currentLabel;
//        public static Dictionary<string, Vertex> graphVertexDic;
//        private static List<string> tree = new List<string>();
//        private static List<double> SCCCount = new List<double>();


//        static void Main(string[] args)
//        {
//            var graph = new BidirectionalGraph<string, Edge<string>>();
//            graphVertexDic = new Dictionary<string, Vertex>();

//            string fileName = "SCC.txt";

//            #region intitlize graph

//            char[] delimiterChars = { ' ', ',', '.', ':', '\t' };
//            int count = 0;

//            using (StreamReader sr = new StreamReader("TestCases\\" + fileName))
//            {
//                String line;
//                // Read and display lines from the file until the end of
//                // the file is reached.
//                while ((line = sr.ReadLine()) != null)
//                {
//                    string[] list = line.Split(delimiterChars, StringSplitOptions.RemoveEmptyEntries);

//                    string v = (list[0]);
//                    string w = (list[1]);
//                    //if(v!=w)
//                    {
//                        if (!graph.ContainsVertex(v))
//                        {
//                            graph.AddVertex(v);
//                            graphVertexDic[v] = new Vertex(v);
//                        }
//                        if (!graph.ContainsVertex(w))
//                        {
//                            graph.AddVertex(w);
//                            graphVertexDic[w] = new Vertex(w);
//                        }
//                        graph.AddEdge(new Edge<string>(v, w));
//                    }




//                    count = count + 1;

//                }

//            }

//            #endregion


//            currentLabel = 0;
//            f = new Dictionary<string, int>();
//            d = new Dictionary<string, int>();

//            #region computed reverse T
//            var tempg = graph.Clone();
//            tempg.RemoveEdgeIf(p => true);
//            foreach (var e in graph.Edges)
//            {
//                var t = e.Source;
//                var s = e.Target;
//                tempg.AddEdge(new Edge<string>(s, t));



//            }
//            #endregion

//            count = 0;
//            #region calucalte f
//            foreach (var v in graph.Vertices)
//            {
//                if (graphVertexDic[v].Exploered == Vertex.Color.white)
//                {
//                    count = count + 1;
//                    Console.WriteLine("Executing for {0} of {1}", graph.Vertices.Count(), count);
//                    DFS(graph, v);

//                }
//            }

//            var final = f.OrderBy(p => p.Value).Reverse().ToList();
//            var duration = d.OrderBy(p => p.Key).ToList();
//            #endregion

//            #region reset value
//            currentLabel = 0;
//            foreach (var keyValuePair in graphVertexDic)
//            {
//                keyValuePair.Value.Exploered = Vertex.Color.white;
//            }
//            f.Clear();
//            d.Clear();
//            duration.Clear();
//            #endregion

//            #region second DFS call
//            foreach (KeyValuePair<string, int> keyValuePair in final)
//            {
//                tree.Clear();
//                if (graphVertexDic[keyValuePair.Key].Exploered == Vertex.Color.white)
//                {
//                    DFS(tempg, keyValuePair.Key);

//                    foreach (string v in tree)
//                    {
//                        //Console.Write("{0},", v);

//                    }
//                    //Console.WriteLine("--->Following form a SCC with count-->" + tree.Count);
//                    SCCCount.Add(tree.Count);
//                }

//            }
//            #endregion
//            var arr = SCCCount.OrderByDescending(p => p).Take(5).ToArray();

//            Console.WriteLine("For an array of length {0} Max SCC Count={1}<{2}<{3}<{4}<{5}", SCCCount.Count, arr[0], arr[1], arr[2], arr[3], arr[4]);

//            Console.ReadLine();
//        }

//        private static void DFS(BidirectionalGraph<string, Edge<string>> graph, string vertex)
//        {
//            var outEdges = from x in graph.Edges
//                           where x.Source == vertex
//                           select x;
//            graphVertexDic[vertex].Exploered = Vertex.Color.greay;
//            currentLabel = currentLabel + 1;

//            d.Add(vertex, currentLabel);
//            tree.Add(vertex);
//            Console.WriteLine("Total edges to run on {0} for vertex {1} ", outEdges.Count(), vertex);
//            foreach (Edge<string> edge in outEdges)
//            {
//                var v = edge.GetOtherVertex(vertex);
//                if (graphVertexDic[v].Exploered == Vertex.Color.white)
//                {

//                    DFS(graph, v);


//                }

//            }
//            graphVertexDic[vertex].Exploered = Vertex.Color.black;
//            currentLabel = currentLabel + 1;

//            f.Add(vertex, currentLabel);



//        }
//    }

//    public class Vertex
//    {

//        public enum Color
//        {
//            white,
//            greay,
//            black
//        } ;
//        public Vertex(string val)
//        {
//            this.Value = val;
//            this.Exploered = Color.white;
//        }

//        public string Value { get; set; }
//        public Color Exploered { get; set; }

//        public override bool Equals(System.Object obj)
//        {
//            // If parameter is null return false.
//            if (obj == null)
//            {
//                return false;
//            }

//            // If parameter cannot be cast to Point return false.
//            Vertex p = obj as Vertex;
//            if ((System.Object)p == null)
//            {
//                return false;
//            }

//            // Return true if the fields match:
//            return p.Value == this.Value;
//        }
//    }
//}
